package a2025_04_12;

public class li_wu_de_zui_da_jia_zhi {
    public int jewelleryValue(int[][] frame) {
        //以某个位置为终点的礼物的最大价值
        // int m=frame.length;
        // int n=frame[0].length;
        // int[][] dp=new int[m+1][n+1];
        // for(int i=1;i<=m;i++){
        //     for(int j=1;j<=n;j++){
        //         dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
        //     }
        // }
        // return dp[m][n];


        //以某个位置为起点到终点的礼物的最大价值
        int m=frame.length;
        int n=frame[0].length;
        int[][] dp=new int[m+1][n+1];

        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                dp[i][j]=Math.max(dp[i+1][j],dp[i][j+1])+frame[i][j];
            }
        }
        return dp[0][0];
    }
}
